package com.currentbp.Interesting.likou.complete;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author baopan
 * @createTime 2024/3/28 22:11
 */
public class T1027longestArithSeqLength {
    /*
给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。
并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。
示例 1：
输入：nums = [3,6,9,12]
输出：4
解释：
整个数组是公差为 3 的等差数列。
示例 2：
输入：nums = [9,4,7,2,10]
输出：3
解释：
最长的等差子序列是 [4,7,10]。
示例 3：
输入：nums = [20,1,15,3,10,5,8]
输出：4
解释：
最长的等差子序列是 [20,15,10,5]。
     */

    /*
    解题思路： todo 超时了
    1、构建一个二维数组，
    如：
   9  4  7  2  10
9  0  5  2  7  -1
4     0  -3  2 -6
7        0   5  -3
2           0  -8
10              0
    2、找出具有相同数字的作为一个集合map集合，然后去掉只有一个数字的
    2.1、如果所有数字都只有1个的话，直接返回2
    2.2、如果还剩下其他的数字，则继续后面的判断
    3、选定一个数字N
    3.1、从i=0，j=i+1开始，找到N，此时长度为2，i=x,j=y
    3.2、在从i=y,j=i+1开始，如果找到N，此时长度+1，以此类推， 如果找不到N，则循环结束
    3.3、返回数字N的长度
     */

    @Test
    public void t1() {
//        System.out.println(longestArithSeqLength(new int[]{3, 6, 9, 12}));
//        System.out.println(longestArithSeqLength(new int[]{9, 4, 7, 2, 10}));
        System.out.println(longestArithSeqLength(new int[]{20, 1, 15, 3, 10, 5, 8}));
    }

    int max = 0;
    /*
    超时了
     */
    public int longestArithSeqLength(int[] nums) {
        if (nums == null || nums.length <= 0) {
            return 0;
        }
        if (nums.length <= 2) {
            return nums.length;
        }

        int[][] diffValues = getDiffValues(nums);
        Map<Integer, Integer> diff2CountMap = getDiffCountMap(diffValues);
        Map<Integer, Integer> newDiff2CountMap = getFilterDiffCountMap(diff2CountMap);
        if (newDiff2CountMap.size() == 0) {
            return 2;
        }

        Set<Integer> diffs = newDiff2CountMap.keySet();
        for (Integer diff : diffs) {
            max = Math.max(getMaxLength(diffValues, diff), max);
        }

        return max;
    }

    /**
     * 按照diff这个公差作为找到最长子序列
     */
    private int getMaxLength(int[][] diffValues, Integer diff) {
        int tempMax = 0;
        for (int i = 0; i < diffValues.length; i++) {
            for (int j = i + 1; j < diffValues.length; j++) {
                if (diff == diffValues[i][j]) {//定位公差为diff的地方
                    tempMax = Math.max(tempMax, getMaxLength2(diffValues, diff, i, j));
                }
            }
        }
        return tempMax;
    }

    /**
     * 根据给定的位置和公差，找出当前子序列的长度
     */
    private int getMaxLength2(int[][] diffValues, Integer diff, int i, int j) {
        int max = 2;
        i = j;
        j = i + 1;
        while (i < diffValues.length && j < diffValues.length) {
            if (diffValues[i][j] == diff) {
                max++;
                i = j;
                j = i + 1;
            } else {
                j = j + 1;
            }
        }

        return max;
    }

    /*
    过滤掉为1的数量
     */
    private Map<Integer, Integer> getFilterDiffCountMap(Map<Integer, Integer> diff2CountMap) {
        Set<Integer> diffs = diff2CountMap.keySet();
        Map<Integer, Integer> result = new HashMap<>();
        for (Integer diff : diffs) {
            if (diff2CountMap.get(diff) != 1) {
                result.put(diff, diff2CountMap.get(diff));
            }
        }
        return result;
    }

    private Map<Integer, Integer> getDiffCountMap(int[][] diffValues) {
        Map<Integer, Integer> result = new HashMap<>();

        for (int i = 0; i < diffValues.length; i++) {
            for (int j = i + 1; j < diffValues.length; j++) {
                if (result.get(diffValues[i][j]) == null) {
                    result.put(diffValues[i][j], 1);
                } else {
                    result.put(diffValues[i][j], result.get(diffValues[i][j]) + 1);
                }
            }
        }

        return result;
    }

    /**
     * 构建二维数组
     */
    private int[][] getDiffValues(int[] nums) {
        int[][] result = new int[nums.length][nums.length];

        for (int i = 0; i < nums.length; i++) {
            for (int j = i; j < nums.length; j++) {
                result[i][j] = nums[i] - nums[j];
            }
        }

        return result;
    }
}
